class Solution {//leetcode76——最小覆盖子串
public:
    string minWindow(string s, string t) {
        string substr;
        int min_len=100001;
        int begin=-1;
        int cnt=0;
        int hash1[128]={0};
        for(auto e:t){
            hash1[e]++;
        }
        int n=t.size();
        int hash2[128]={0};

        for(int left=0,right=0;right<s.size();right++){
            //进窗口
            char in=s[right];
            hash2[in]++;
            if(hash2[in]<=hash1[in]) cnt++;
            //出窗口
            while(cnt==n){
                char out=s[left];
                if(min_len>right-left+1){
                    begin=left;
                    min_len=right-left+1;
                }
                if(hash2[out]<=hash1[out]) cnt--;
                hash2[out]--;
                left++;
            } 
        }

        if(begin!=-1) substr=s.substr(begin,min_len);
        return substr;
    }
};